package com.yulan.backTrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 51. N皇后
 */
public class NQuenes {

    int[] x ;
    int n;
    List<List<String>> res;
    int sum = 0;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        x = new int[this.n+1];
        res = new ArrayList<>();
        dfs(0);
        return res;
    }

    public void dfs(int t){ // 第t层树
        if(t >= n){//找到了一个可行解
            int[] tmp_x = new int[n];
            for(int i = 0; i<n; i++){
                tmp_x[i] = x[i];
            }
            res.add(buildAns(tmp_x));
            sum++;
            return;
        }

        for(int i = 0;i<n;i++){
            x[t] = i;
            if(isValid(t)) dfs(t+1);
        }
    }

    //讲一个结果构造出一个List<String>
    public List<String> buildAns(int[] x){
        List<String> ans = new ArrayList<>();
        //(i,x[i])表示皇后的坐标
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ;i<x.length;i++){
            for(int j = 0;j<x[i];j++)
                sb.append(".");
            sb.append("Q");
            for(int k = x[i]+1;k<n;k++)
                sb.append(".");
            ans.add(sb.toString());
            sb.delete(0,sb.length());
        }
        return ans;
    }

    //检查下一个皇后放在第t行行不行
    public boolean isValid(int t){
        for(int i = 0;i< t; i++){
            if(x[t] == x[i] || Math.abs(i - t) == Math.abs(x[i] - x[t])) // 同一行，或者斜率等于 1 或 -1
                return false;
        }
        return true;
    }

    @Test
    public void test(){
        for(List<String> list: solveNQueens(4)){
            for(String str : list){
                System.out.println(str);
            }
        }
        System.out.println(sum);
    }
}
